Graph Neural Networks (GNN)
By Prof. Seungchul Lee
http://iai.postech.ac.kr/
Industrial AI Lab at POSTECH
http://iai.postech.ac.kr/
Industrial AI Lab at POSTECH
Table of Contents
1. Graph ¶
- abstract relations, topology, or connectivity
- Graphs $G(V,E)$
- $V$: a set of vertices (nodes)
- $E$: a set of edges (links, relations)
- weight (edge property)
- distance in a road network
- strength of connection in a personal network
- Graphs model any situation where you have objects and pairwise relations (symmetirc or asymmetirc) between the objects
| Vertex | Edge | |
|---|---|---|
| People | like each other | undirected |
| People | is the boss of | directed |
| Tasks | cannot be processed at the same time | undirected |
| Computers | have a direct network connection | undirected |
| Airports | planes flies between them | directed |
| City | can travel between them | directed |
1.1. Type of Graph ¶
Undirected Graph vs. Directed Graph
- Undirected graph
- Edges of undirected graph points both ways between nodes
- ex) Two-way road
- Directed graph
- A graph in which the edges are directed
- ex) One-way raod
Weighted Graph
- A graph with edges assigned costs or weights
- Also called 'Network'
- ex) connection between cities, length of road, circuit element capacity, communication network usage fee, etc.
1.2. Graph Representation¶
Graph and Adjacency Matrix
- Simple undirected graph consist of only nodes and edges
- Graph can be represented as adjacency matrix $A$
- Adjacency matrix $A$ indicates adjacent nodes for each node
- Need (number of nodes) $ \times$ (number of nodes) shape matirx to represent adjacency matirx of undirected graph
- Symmetirc matirx
1.3. Adjacent Matrix¶
- Undirected graph $G = (V,E)$
- Directed graph $G = (V,E)$
In [7]:
# !pip install networkx
In [1]:
import networkx as nx
import matplotlib.pyplot as plt
%matplotlib inline
Graph.add_edgeIn [2]:
g = nx.Graph()
g.add_edge('a', 'b')
g.add_edge('b', 'c')
g.add_edge('a', 'c')
g.add_edge('c', 'd')
In [3]:
# draw a graph with nodes and edges
nx.draw(g)
plt.show()
In [4]:
# draw a graph with node labels
pos = nx.spring_layout(g)
nx.draw_networkx_nodes(g, pos)
nx.draw_networkx_edges(g, pos)
nx.draw_networkx_labels(g, pos)
plt.axis('off')
plt.show()
Graph.add_nodes_fromGraph.add_edges_fromIn [5]:
G = nx.Graph()
G.add_nodes_from([1,2,3,4])
G.add_edges_from([(1,2),(1,3),(2,3),(3,4)])
# plot a graph
pos = nx.spring_layout(G)
nx.draw(G, pos, node_size = 500)
nx.draw_networkx_labels(G, pos, font_size = 10)
plt.show()
In [6]:
print(nx.number_of_nodes(G))
print(nx.number_of_edges(G))
In [7]:
G.nodes()
Out[7]:
In [8]:
G.edges()
Out[8]:
In [9]:
A = nx.adjacency_matrix(G)
print(A)
print(A.todense())
1.4. Degree¶
Degree of Undirected Graph
- the degree of vertex in a graph is the number of edges connected to it
- denote the degree of vertex $i$ by $d_{i}$
- for an undirected graph of $n$ vertices
$$ d_i = \sum_{j=1}^{n} \; A_{ij} $$
- Degree matrix $D$ of adjacent matrix $A$
$$D = \text{diag}\{d_1, d_2, \cdots \}$$
- Example
$$A = \begin{bmatrix} 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 \end{bmatrix} \qquad \Rightarrow \qquad D = \begin{bmatrix} 3 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 2 & 0 \\ 0 & 0 & 0 & 2 \end{bmatrix} $$
1.5. Self-connecting Edges¶
$$A = \begin{bmatrix} 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 \end{bmatrix} \qquad \Rightarrow \qquad A+I = \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 1 \end{bmatrix} \qquad \Rightarrow \qquad \tilde D = \begin{bmatrix} 4 & 0 & 0 & 0 \\ 0 & 2 & 0 & 0 \\ 0 & 0 & 3 & 0 \\ 0 & 0 & 0 & 3 \end{bmatrix} $$
1.6. Neighborhood Normalization¶
Some nodes have many edges, but some don't
Adding $I$ is to add self-connecting edges
Considering neighboring nodes in the normalized weights
to prevent numerical instabilities and vanishing/exploding gradients in order for the model to converge
1) (First attempt) Normalized $\tilde A$
$$\tilde D^{-1}(A+I)$$2) Normalized $\tilde A$
$$\tilde A = \tilde D^{-1/2}(A+I) \tilde D^{-1/2}$$Now we consider a feature matrix $H$
- Weighted sum (or averaging) of neighboring features
In [10]:
import numpy as np
In [11]:
A = np.array([[0,1,1,1],
[1,0,0,0],
[1,0,0,1],
[1,0,1,0]])
A_self = A + np.eye(4)
print(A_self)
In [12]:
D = np.array(A_self.sum(1)).flatten()
D = np.diag(D)
print(D)
1) (First attempt) Normalized $\tilde A$
$$\tilde D^{-1}(A+I)$$- It is not symmetric.
In [13]:
A_norm = np.linalg.inv(D).dot(A_self)
print(A_norm)
2) Normalized $\tilde A$
$$\tilde A = \tilde D^{-1/2}(A+I) \tilde D^{-1/2}$$Now it is symmetric.
(Skip the details)
In [14]:
D = np.array(A_self.sum(1))
D_half_norm = np.power(D, -0.5).flatten()
D_half_norm = np.diag(D_half_norm)
A_self = np.asmatrix(A_self)
D_half_norm = np.asmatrix(D_half_norm)
A_half_norm = D_half_norm*A_self*D_half_norm
print(A_half_norm)
2. Graph Convolution Network (GCN)¶
2.1. Convolution¶
- In previous CNN lecture CNN has two characteristics, preserving the spatial structure and weight sharing
- To apply convolution in graph network, graph also has to conpensate that characteristics too
Convolution Layer
- In CNN, convolution layer preserve the spatial structure of input
- It convolve over all spatial locations
- Extract features for each convolution layer
Weight Sharing
- Reduce the number of parameters by weight sharing
- Within the same layer, the same filter will be used throughout image
2.2. Connection between CNN and GCN¶
- GCNs perform similar operations where the model learns the features by inspecting neighboring nodes
- The major difference between CNNs and GCNs is that CNNs are specially built to operate on regular (Euclidean) structured data, while GCNs operate for the graph data that the number of nodes connections vary and the nodes are unordered (irregular on non-Euclidean structured data)
2.3. Basics of GCN¶
- Similar to CNN, GCN updates each node with their adjacent nodes
- Unlike CNN, each node of GCN has different number of adjacent nodes
- Indicate adjacent nodes of each node by adjacency matrix $A$
- Basic process (or terminology) of GCN
- Message: information passed by neighboring nodes to the central node
- Aggregate: collect information from neighboring nodes
- Update: embedding update by combining information from neighboring nodes and from itself
1) Message Aggregation from Local Neighborhood
2) Update
Adding a non-linear function: $k^{\text{th}}$ layer
$$ \begin{align*} H^{(k+1)} &= f \left( A, H^{(k)} \right) \\ & = \sigma \left( A H^{(k)} \, W \right) \end{align*} $$- $h_1^{(k)}$: feature matirx of first node in $k^{th}$ layer
- $W^{(k)}$: weight of $k^{th}$ layer
- Weight sharing: share same weight for each layer
- In the same layer, each node is updated similarly, so it shares the same weight
- weight sharing enchance computing complexity and time
- Weight sharing: share same weight for each layer
2.4. Further Improvements for GCN¶
1) Message Passing with Self-Loops
- As a simplification of the neural message passing approach, it is common to add self-loops to the input graph and omit the explicit update step
2) Neighborhood Normalization
- The most basic neighborhood aggregation operation simply takes the sum of the neighbor embedding.
- One issue with this approach is that it can be unstable and highly sensitive to node degrees.
- One solution to this problem is to simply normalize the aggregation operation based upon the degrees of the nodes involved.
- The simplest approach is to just take a weighted average rather than sum.
Finally Graph Convolutional Networks
- For each layer, the feature matrix and weight matrix are multiplied to create the next feature matrix
In [15]:
import networkx as nx
import matplotlib.pyplot as plt
%matplotlib inline
G = nx.Graph()
G.add_nodes_from([1, 2, 3, 4, 5, 6])
G.add_edges_from([(1, 2), (1, 3), (2, 3), (1, 4), (4, 5), (4, 6), (5, 6)])
nx.draw(G, with_labels = True)
plt.show()
In [16]:
A = nx.adjacency_matrix(G).todense()
print(A)
Assign feature vector H, so that it can be separated into two groups
In [17]:
H = np.matrix([1,0,0,-1,0,0]).T
print(H)
Product of Adjacency Matrix and Node Features Matrix represents the sum of neighboring node features
In [18]:
A*H
Out[18]:
In [19]:
A_self = A + np.eye(6)
print(A_self)
Similar to data pre-processing for any Neural Networks operation, normalize the features to prevent numerical instabilities and vanishing / exploding gradients in order for the model to converge
In [20]:
D = np.array(A_self.sum(1))
print(D)
In [29]:
D_half_norm = np.power(D, -0.5).flatten()
D_half_norm = np.diag(D_half_norm)
A_self = np.asmatrix(A_self)
D_half_norm = np.asmatrix(D_half_norm)
A_half_norm = D_half_norm*A_self*D_half_norm
print(A_half_norm)
In [22]:
A_half_norm*H
Out[22]:
Build 2-layer GCN using ReLU as the activation function
In [28]:
np.random.seed(1)
W1 = np.random.randn(1, 4) # input: 1 -> hidden: 4
W2 = np.random.randn(4, 2) # hidden: 4 -> output: 2
def relu(x):
return np.maximum(0, x)
def gcn(A, H, W):
D = np.array((A + np.eye(6)).sum(1))
D_half_norm = np.diag((np.power(D, -0.5)).flatten())
H_new = D_half_norm*A_self*D_half_norm*H*W
return relu(H_new)
H1 = gcn(A, H, W1)
H2 = gcn(A, H1, W2)
print(H2)
2.5. Readout: Permutation Invariance¶
Adjacency matrix can be different even though two graph has the same network structure
- Even if the edge information between all nodes is the same, the order of values in the matrix may be different due to rotation and symmetry
Therefore, in graph-level representation,Readout layer makes this permutation invariant by multiplying MLP
- Node-wise summation
2.6. Overall Structure of GCN¶
- Graph information with feature matrix and adjacency matrix input to GCN
- Graph Convolution Layer
- Update information of each node according to their adjacency matrix
- Collect all node information with MLP and determine a certain value for regression or classification in readout layer
2.7. Three Types of GNN Problem¶
Task 1: Node classification
Task 2: Edges prediction
Task 3: Graph classification
3. Lab 1: Node Classification using Graph Convolutional Networks¶
3.0. List of GNN Python Libraries¶
- PyTorch Geometric
- PyG
- Built upon PyTorch
- Deep Graph Library (DGL)
- Based on PyTorch, TensorFlow or Apache MXNet.
- Graph Nets
- DeepMind’s library for building graph networks in Tensorflow and Sonnet
- Spektral
- Based on the Keras API and TensorFlow 2
- We will use this one for demo
In [ ]:
# !pip install spektral==0.6.0
# !pip install tensorflow==2.2.0
# !pip install keras==2.3.0
In [1]:
import numpy as np
import networkx as nx
from tensorflow.keras.utils import to_categorical
from spektral.layers import GraphConv
from tensorflow.keras.models import Model
from tensorflow.keras.layers import Input, Dropout
from tensorflow.keras.optimizers import Adam
import tensorflow as tf
from tensorflow.keras.regularizers import l2
from collections import Counter
from sklearn.manifold import TSNE
import matplotlib.pyplot as plt
In [2]:
classes = ['Case_Based',
'Genetic_Algorithms',
'Neural_Networks',
'Probabilistic_Methods',
'Reinforcement_Learning',
'Rule_Learning',
'Theory']
In [11]:
labels_encoded = np.load('./data_files/cora_labels_encoded.npy')
nodes = np.load('./data_files/cora_nodes.npy')
edge_list = np.load('./data_files/cora_edges.npy')
X = np.load('./data_files/cora_features.npy')
data_mask = np.load('./data_files/cora_mask.npy')
N = X.shape[0]
F = X.shape[1]
print('X shape: ', X.shape)
print('\nNumber of nodes (N): ', N)
print('\nNumber of features (F) of each node: ', F)
print('\nCategories: ', classes)
num_classes = len(classes)
print('\nNumber of classes: ', num_classes)
3.2 Train/Validation/Test Data Splitting¶
In case of GCN, it is possible to train with small number of data compared to supervised method because it is semi-supervised method. Therefore, in this task, train dataset will consist of 20 data for each class. Likewise, execute validation and test with 500 validation dataset and 1000 test dataset.
In [4]:
# Load index of node for train model
train_mask = data_mask[0]
# Load index of node for validate model
val_mask = data_mask[1]
# Load index of node for test model
test_mask = data_mask[2]
In [5]:
print("All Number of Node for Node Classification: ", len(labels))
print("\n")
print("Number of Trainig Data: ", np.sum(train_mask))
print("\n")
print("Number of Validation Data: ", np.sum(val_mask))
print("\n")
print("Number of Test Data: ", np.sum(test_mask))
3.3 Initializing Graph G¶
In [6]:
G = nx.Graph(name = 'Cora')
G.add_nodes_from(nodes)
G.add_edges_from(edge_list)
print('Graph info: ', nx.info(G))
3.4 Construct and Normalize Adjacency Matrix A¶
3.4.1 Insert self-loops to A¶
In [7]:
A = nx.adjacency_matrix(G)
I = np.eye(A.shape[-1], dtype=A.dtype)
A_self = A + I
3.4.2 Normalizing term , $D^{-1/2}AD^{-1/2}$¶
In [8]:
degree = np.array(A_self.sum(1))
D_half_norm = np.power(degree, -0.5).flatten()
D = np.diag(D_half_norm)
print('D:\n', D)
DAD = D * A_self * D
print('\nDAD:\n', DAD)
DAD = np.array(DAD, dtype = np.float32)
X = np.array(X, dtype = np.float32)
3.5 GCN Model¶
In [58]:
channels = 16
dropout = 0.5
l2_reg = 5e-4
learning_rate = 1e-2
epochs = 100
es_patience = 10
X_in = Input(shape = (F, ))
fltr_in = Input((N, ), sparse = True)
dropout_1 = Dropout(dropout)(X_in)
graph_conv_1 = GraphConv(channels,
activation = 'relu',
kernel_regularizer = l2(l2_reg),
use_bias = False)([dropout_1, fltr_in])
dropout_2 = Dropout(dropout)(graph_conv_1)
graph_conv_2 = GraphConv(num_classes,
activation = 'softmax',
use_bias = False)([dropout_2, fltr_in])
model = Model(inputs = [X_in, fltr_in], outputs = graph_conv_2)
optimizer = Adam(lr = learning_rate)
model.compile(optimizer = optimizer,
loss = 'categorical_crossentropy',
weighted_metrics = ['acc'])
model.summary()
3.6 Train Model¶
In [60]:
validation_data = ([X, DAD], labels_encoded, val_mask)
model.fit([X, DAD],
labels_encoded,
sample_weight = train_mask,
epochs = epochs,
batch_size = N,
validation_data = validation_data,
shuffle = False,)
Out[60]:
3.7 Model Evaluation¶
In [42]:
from sklearn.metrics import confusion_matrix
import matplotlib.pyplot as plt
X_te = X[test_mask]
A_te = DAD[test_mask,:][:,test_mask]
y_te = labels_encoded[test_mask]
y_pred = model.predict([X_te, A_te], batch_size = N)
cm = confusion_matrix(np.argmax(y_te, axis = 1), np.argmax(y_pred, axis = 1))
print('Confusion matrix')
print(cm)
# plot_confusion_matrix(np.argmax(y_te, axis=1), np.argmax(y_pred, axis=1), classes, fontsize=15)
In [43]:
plt.figure()
plt.imshow(cm, interpolation = 'nearest', cmap = plt.cm.Blues)
fmt = 'd'
thresh = cm.max() / 2.
for i in range(cm.shape[0]):
for j in range(cm.shape[1]):
plt.text(j, i, format(cm[i, j], fmt), ha = "center", va = "center", color = "white" if cm[i, j] > thresh else "black", fontsize = 15)
plt.colorbar()
plt.tight_layout()
plt.show()
3.8 T-SNE¶
In [15]:
layer_outputs = [layer.output for layer in model.layers]
activation_model = Model(inputs = model.input, outputs = layer_outputs)
activations = activation_model.predict([X,DAD],batch_size = N)
x_tsne = TSNE(n_components = 2).fit_transform(activations[3])
In [16]:
def plot_tSNE(labels_encoded,x_tsne):
color_map = np.argmax(labels_encoded, axis = 1)
plt.figure(figsize = (10,10))
for cl in range(num_classes):
indices = np.where(color_map == cl)
indices = indices[0]
plt.scatter(x_tsne[indices,0], x_tsne[indices, 1], label = cl)
plt.legend()
plt.show()
plot_tSNE(labels_encoded,x_tsne)
4. Useful Resources for Further Study ¶
In [1]:
%%html
<center><iframe src="https://www.youtube.com/embed/fOctJB4kVlM?rel=0"
width="560" height="315" frameborder="0" allowfullscreen></iframe></center>
In [2]:
%%html
<center><iframe src="https://www.youtube.com/embed/ABCGCf8cJOE?rel=0"
width="560" height="315" frameborder="0" allowfullscreen></iframe></center>
In [3]:
%%html
<center><iframe src="https://www.youtube.com/embed/0YLZXjMHA-8?rel=0"
width="560" height="315" frameborder="0" allowfullscreen></iframe></center>
In [4]:
%%html
<center><iframe src="https://www.youtube.com/embed/ex2qllcVneY?rel=0"
width="560" height="315" frameborder="0" allowfullscreen></iframe></center>
In [5]:
%%html
<center><iframe src="https://www.youtube.com/embed/YL1jGgcY78U?rel=0"
width="560" height="315" frameborder="0" allowfullscreen></iframe></center>
In [6]:
%%html
<center><iframe src="https://www.youtube.com/embed/8owQBFAHw7E?rel=0"
width="560" height="315" frameborder="0" allowfullscreen></iframe></center>
In [7]:
%%html
<center><iframe src="https://www.youtube.com/embed/R67-JxtOQzg?rel=0"
width="560" height="315" frameborder="0" allowfullscreen></iframe></center>
University cources:
- COMP766 at McGill (https://cs.mcgill.ca/~wlh/comp766/)
- Alelab Alelab (https://www.youtube.com/channel/UC_YPrqpiEqkeGOG1TCt0giQ/playlists)
In [1]:
%%javascript
$.getScript('https://kmahelona.github.io/ipython_notebook_goodies/ipython_notebook_toc.js')